package simple;

import sword.offer.common.GenerateTree;
import sword.offer.common.Node;
import sword.offer.common.TreeNode;

import java.util.*;

/**
 * leet 101
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class SymmetricTree {

    public static void main(String[] args) {

        TreeNode node = GenerateTree.generateTree1(Arrays.asList(1, 2, 2, 3, 4, 4, 3));
        Solution solution = new Solution();
        solution.isSymmetric(node);
    }
    /**
     * 第一种方法，使用DFS。
     * 判断该树是否对称，即对该树的左右子节点进行比较。
     * 当左子树的左节点 和 右子树的右结点相同 且 左子树的右结点 与 右子树的左节点相同。那么两颗子树就是镜像子树。
     * 当两颗子树互为镜像子树的时候，这颗数就是对称的。
     * */
    public boolean isSymmetric(TreeNode root) {
        return isMirrorTree(root.left, root.right);
    }

    public boolean isMirrorTree(TreeNode node1, TreeNode node2){
        if(node1 == null || node2 == null){
            return node1 == node2;
        }
        return node1.val == node2.val && isMirrorTree(node1.left, node2.right) && isMirrorTree(node1.right, node2.left);
    }


    /**
     * BFS的方法
     * 思维总是被约束的。我之前自己思考过一种BFS的方法来解答本题。通过层序遍历，将每一层的结点依次放入到一个双端队列中。
     * 然后将头尾两个结点出队进行比较。这就意味着，需要把每一层的所有结点都放到一个额外的双端队列中。
     * 而且还需要增加一个循环，因为我们需要把每层的结点单独拿出来。BFS中只是按照每层结点的顺序进行遍历的，所以只有一层循环。
     * */
    static class Solution{
        public boolean isSymmetric(TreeNode root) {
            if (Objects.isNull(root)) {
                return false;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root.left);
            queue.add(root.right);
            while (!queue.isEmpty()){
                TreeNode node1 = queue.poll();
                TreeNode node2 = queue.poll();
                if(node1 == null && node2 == null) {continue;}
                if(node1 == null || node2 == null) {return false;}
                if(node1.val != node2.val) {return false;}
                /*
                * 重点在这里,这样，结点顺序就变成了 左子树的左节点、 右子树的右节点、左子树的右节点、右子树的左节点；
                * 但是这里会有大量的重复数据出现。比如我们在进入这个循环之前，在队列中加入了两个根节点
                * 根节点的左和右  右和左 被加入到了该队列，即重复了。那么后续的结点都会重复。
                * */
                queue.add(node1.left);
                queue.add(node2.right);
                queue.add(node1.right);
                queue.add(node2.left);
            }
            return true;
        }
    }

    /**
     * BFS的另外一种思路,就是正常的从左至右按顺序入队，然后出队时做判断
     * */
    class Solution1{
        public boolean isSymmetric(TreeNode root) {
            if (Objects.isNull(root)) {
                return false;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root.left);
            queue.offer(root.right);
            while (!queue.isEmpty()) {
                List<Integer> list = new ArrayList<>();
                Queue<TreeNode> tempQueue = new LinkedList<>();
                while (!queue.isEmpty()) {
                    TreeNode node = queue.poll();
                    list.add(Objects.isNull(node) ? Integer.MIN_VALUE : node.val);
                    if (Objects.nonNull(node)) {
                        tempQueue.add(node.left);
                        tempQueue.add(node.right);
                    }
                }
                if (!isSymmetric(list)) {
                    return false;
                }
                list.clear();
                queue = tempQueue;
            }
            return true;
        }

        boolean isSymmetric(List<Integer> list) {
            int i = 0;
            int j = list.size() - 1;
            while (i < j) {
                if(!list.get(i++).equals(list.get(j--))) {
                    return false;
                }
            }
            return true;
        }
    }
}
